\chapter{Cooperazione in P2P}
In un sistema P2P il Free Riding consiste nella presenza di peer che non
partecipano alla comunità fornendo dei servizi agli altri nodi, ma che
semplicemente si limitano a utilizzare la rete senza portarne alcun beneficio,
il primo problema di questo tipo non è relativo all'ambiente informatico
ed è chiamato la Tragedia dei Commons, pascoli comuni in America privi di una
regolamentazione e che ha portato alla rovina dei pascoli dovuti al
comportamento egoista
ed errato dell'uso delle risorse.\\
Il problema del Free Riding non può essere risolto introducendo delle regole, ma
far si che il rispetto delle regole comporti un vantaggio al peer nell'uso del
sistema. Utilizzando la {\bf Teoria dei giochi} e introducendo il meccanismo
della {\bf Reciprocità}, ovvero un peer per usufruire di un servizio deve a sua
volta offrirne uno in cambio.
\section {Teoria dei Giochi}
All'interno della rete P2P è possibile riconoscere:
\begin{itemize}
\item Strategie
\item Individui "razionali" il cui comportamento è finalizzato al beneficio
personale, quindi analizza le diverse strategie e sceglie quella che massimizza
il proprio tornaconto.
\end{itemize}
Utilizzando la Teoria dei Giochi è possibile studiare per esempio il
comportamento di due individui che giocano a Pari e Dispari, presi due individui
A e B e la scelta P o D e vittoria =1  e sconfitta =0 si ha un albero delle
scelte in cui si dimostra che se le scelte sono indipendenti l'una dall'altra
allora i due individui hanno la stessa possibilità di vincere a prescindere
dalla scelta da loro fatta. Si può realizzare una tabella corrispondente,
definita {\bf Forma Strategica}.

\subsection{Strategia Dominata}
All'interno di una Forma strategica si definisce {\bf Strategie Dominante},
ovvero quella vincente indipendentemente dalla scelta dell'avversario, quindi
che massimizza il profitto e l'esatto opposto, la {\bf Strategia Dominata}.

\begin{center}
\begin{tabular}{ | l | l |l|l| }
\hline
A/B&S4& S5& S6 \\ \hline
S1&2,0& 4,1& 5,2 \\ \hline
S2&3,1& 3,2& 2,1 \\ \hline
S3&1,4& 2,2& 0,3 \\ \hline
\end{tabular}
\end{center}
In questo caso rispetto al giocatore A la strategia Dominata è S3 mentre non è
possibile trovare una relazione di dominanza tra  S1 e S2.\\
Invece rispetto al giocatore B la strategia Dominata è S4 mentre non è possibile
trovare una relazione di dominanza tra  S5 e S6.\\
Quindi se entrambi i giocatori sono razionali si ottiene il seguente risultato:

\begin{center}
\begin{tabular}{ | l | l |l|}
\hline
A/B& S5& S6 \\ \hline
S1& 4,1& 5,2 \\ \hline
S2& 3,2& 2,1 \\ \hline
\end{tabular}
\end{center}
Rispetto ad A S2 è dominata da S1, che quindi risulta essere la Dominante,
invece per B la Dominante è S6.

\subsection{Dilemma del Prigioniero}
Il gioco del Dilemma del Prigioniero ci sono due complici di un reato che
vengono arrestati e interrogati separatamente dalla polizia. A ciascuno viene
concessa la possibilità di confessare in cambio di una riduzione della pena.\\
Le situazioni sono le seguenti:
\begin{itemize}
\item Se confessano entrambi i prigionieri allora vengono condannati a 4 anni
ciascuno.
\item Se nessuno dei due confessa allora vengono condannati a 2 anni ciascuno.
\item Se solo uno confessa, il primo viene liberato e l'altro condannato a 5
anni di carcere.
\end{itemize}
La Forma Strategica risultante considerando gli sconti di pena rispetto al caso
peggiore è la seguente:
\begin{center}
\begin{tabular}{ | l | l |l|}
\hline
A/B& Non Confessa& Confessa \\ \hline
Non Confessa  & 3,3& 0,5 \\ \hline
Confessa & 5 0 & 1,1 \\ \hline
\end{tabular}
\end{center}
Considerando A la strategia dominante è quella di confessare, vale lo stesso
anche per B, quindi se entrambi i prigionieri sono razionali confessano entrambi
e quindi guadagnano 1 anno ciascuno.\\
Questo gioco evidenza il problema che non conoscendo le scelte altrui si
predilige un guadagno minimo per tutti i giocatori, quando invece dal punto di
vista teorico c'è una possibilità di guadagno maggiore per tutti, nel caso del
Dilemma del Prigioniero il non confessare entrambi comporterebbe un guadagno totale di
6 per il sistema, contro i 2 minimi ma ripartiti equamente e i 5 nel caso non
equo.\\
Introducendo un incentivo sarebbe possibile indurre un giocatore razionale a
compiere la scelta migliore per il sistema.\\
Se consideriamo che il gioco non sia singolo ma ci sono più iterazioni e un
meccanismo di vendetta {\bf Tit For Tat}, in base alla scelta effettuata
precedente dall'altro prigioniero ci si può vendicare o meno. Questa strategia
risulta ottimale nel caso in cui entrambi i prigionieri decidano di non
confessare, ottimizzando così il risultato, altrimenti negli altri casi si
converge alla scelta razionale, ovvero la confessione di entrambi.

\section {Reciprocità Indiretta}
Al contrario del Dilemma del Prigioniero in cui la reciprocità è diretta, iò caso della {\bf Reciprocità Indiretta} è maggiormente utilizzabile in sistemi di grandi dimensioni, in un sistema complesso, come nel P2P, si offre un servizio e una eventuale ricompensa può essere ricevuta indirettamente da altri nodi della rete.
%TODO Inserisci Definizione di Reciprocità Indiretta
Ogni giocatore ha un punteggio s ed una strategia k, se un giocatore coopera solamente se il punteggio del ricevente è maggiore o uguale alla strategia del donatore, se si collabora aumenta il punteggio personale, altrimenti diminuisce.\\
Al termine della generazione ogni giocatore genera dei discendenti, in proporzione al proprio punteggio e con la stessa strategia.\\
%TODO Fare esempio che è sulle slide
Una strategia zero rappresenta la strategia ottimale, eventuali soggetti con strategia alta, quindi poco collaborativi tengono a sparire con l'avanzare delle generazioni, visto che il numero di figli è proporzionale al punteggio e un giocatore con una strategia alta tende ad avere un punteggio basso, visto che viene abbassato ogni volta che si rifiuta di collaborare.\\
E' stato ricreato lo stesso esperimento introducendo però delle perturbazioni nella generazione della discendenza.

\chapter{Valutazione della reputazione in reti P2P}
Valutare la reputazione in una rete P2P è molto complesso visto che la rete è dinamnica e di grandi dimensioni, non è possibile avere informazioni sullo stato globale e utilizza replicazione e frammentazione dei dati per la protezione della privacy.\\
E' possibile effettuare degli attacchi alla rete P2P in modo tale da compromettere l'intero sistema, ad esempio attacchi Sybyl effettuati duplicando identità malevole al fine di influenzare negativamente la rete, oppure attacchi Eclipse in cui dei nodi malevoli oscurano la comunicazione all'interno della rete, ed infine attacchi collusivi di gruppo.\\
\section{Web of Trust}
Il problema delle reti p2p consiste nella facilità nell'ottenere nuove identità, cioè il fenomeno del {\bf whitewashing}. Per questo motivo ai nuovi utenti della rete viene riservato il peggiore dei trattamenti e al contrario si premiano i peer più collaborativi.Se ogni peer valuta i peer con cui ha interagito, creando così delle raccomandazioni, a partire da questo meccanismo di raccomandazioni si può creare un grafo definito {\bf Web of Trust}.\\
A partire da un sistema di reputazione locale si può generalizzare una reputazione globale all'interno del sistema, attraverso il concetto di {\bf transitività della fiducia}.
\doppioCapo
I principi alla base del meccanismo di reputazione sono:
\begin{itemize}
\item Condivisione e rispetto delle regole.
\item Anonimato di chi rilascia il feedback in modo tale da evitare ritorsioni.
\item Nessun trattamento particolare per i nuovi entrati, i quali devono guadagnarsi la reputazione.
\item Overhead minimo per l'intero sistema.
\item Robusti contro gli attacchi collettivi.
\end{itemize}
Una volta identificati degli eventuali nodi ``buoni'' allora questi possono essere privilegiati rispetto agli altri, per esempio il PageRank dà un maggiore rating o in una rete P2P si hanno delle code preferenziali.

\section{EigenTrust}
{\bf EigenTrust} è un algoritmo per il calcolo della reputazione utilizzato nelle reti di File-Sharing. Un coefficiente rappresenta la fiduca locale e valuta il numero di interazioni locale avvenute, ogni interazione avvenuta successo incrementa questo coefficiente, altrimenti lo si decrementa. Utilizzando tutte i coefficienti locali è poi possibile calcolare ed assegnare ad un peer un punteggio globale.\\
Questo sistema è ispirato a PageRank.\\
L'uso del valore di Trust Globale dovrebbe permettere di poter isolare i peer malevoli, inoltrando le richieste soltanto verso i nodi con una maggiore reputazione, è nell'interesse di tutti i peer mantenere la rete pulita, in quanto i nodi traggono del vantaggio nel ripulire la rete, mantendo la loro reputazione invariata e positiva senza incorrere in nodi malevoli che potrebbero falsare i valori della fiducia.\\
L'idea da cui si parte è quella di {\bf Local trust value}, definito come $c_{ij}=\frac{max(s_{ij},0)}{\sum_j max(s_{ij},0)}$.
%TODO immagini pag 13/35
Questi valori di fiducia vengono normalizzati in modo che la somma degli archi uscenti da un nodo sia 1.\\
La valutazione di un nodo può essere ottenuta anche come aggregazione delle valutazioni locali effettuate dai vicini del nodo considerato, $t_{ik}=\sum_j c_{ij}c_{jk}$. Posso scrivere tutto questo in forma matriciale e allargando le informazioni ai vicini dei vicini e così via il risultato finale converge al {\bf Global Trust} di un peer.
%TODO immagini
\subsection{Nodi pre-trusted}
Per creare una Eigen-trust si ha bisogno di partire con dei nodi {\bf pre-trusted}, ovvero dei peer che si conoscono già come autorevoli fin dall'inizio del sistema. Questi nodi hanno anche la particolarità di evitare attacchi collusivi da parte di gruppi di nodi maligni.
\subsection{Attacchi Collusivi}
Il problema di Attacchi Collusivi consiste in un insieme di nodi malevoli all'interno della rete che costituiscono una comunità e che collaborano tra di loro per poter aumentare il loro punteggio globale per poter poi compromettere l'efficienza della rete.\\
%TODO FINIRE
\subsection{Versioni sicure e distribuite}
Dato che un peer malevolo può mentire nel valutare la reputazione di altri peer o la propria, la reputazione viene ottenuta contattando alcuni nodi responsabili, detti {\bf Score Manager}, effettuando poi un voto a maggioranza.
\doppioCapo
Essendo in una rete p2p, è vero che i nuovi nodi avranno il peggiore dei trattamenti possibile, ma a volte verrà loro inoltrata una richiesta anche se la loro reputazione è nulla, per evitare di sovraccaricare di richieste i peer autorevoli e permettendo all'intera comunità di incrementare la propria reputazione. Ad ogni peer viene associata una probabilità di instradamento della richiesta proporzionale alla sua reputazione.
\subsection{Esempi di Eigen Trust}
Sono stati eseguiti diversi esperimenti con EigenTrust:
...



